(display "\n========================================\n")
(define (encode-symbol symbol tree)
    (cond ((leaf? tree)                                         ; 如果已经到达叶子节点，那么停止积累
            '())
          ((symbol-in-tree? symbol (left-branch tree))          ; 符号在左分支(左子树)，组合起 0
            (cons 0
                  (encode-symbol symbol (left-branch tree))))
          ((symbol-in-tree? symbol (right-branch tree))         ; 符号在右分支(右子树)，组合起 1
            (cons 1
                  (encode-symbol symbol (right-branch tree))))
          (else                                                 ; 给定符号不存在于树，报错
            (error "This symbol not in tree: " symbol))))

(define (symbol-in-tree? given-symbol tree)
    (not
        (false?
            (find (lambda (s)                   ; 使用 find 函数，在树的所有符号中寻找给定符号
                      (eq? s given-symbol))
                  (symbols tree)))))            ; 取出树中的所有符号

(define (make-leaf symbol weight)
    (list 'leaf symbol weight))

(define (leaf? object)
    (eq? (car object) 'leaf))

(define (symbol-leaf x)
    (cadr x))

(define (weight-leaf x)
    (caddr x))

(define (left-branch tree)
    (car tree))

(define (right-branch tree)
    (cadr tree))

(define (make-code-tree left right)
    (list left
          right
          (append (symbols left) (symbols right))
          (+ (weight left) (weight right))))

(define (symbols tree)
    (if (leaf? tree)
        (list (symbol-leaf tree))
        (caddr tree)))

(define (weight tree)
    (if (leaf? tree)
        (weight-leaf tree)
        (cadddr tree)))

(define (encode message tree)
    (if (null? message)
        '()
        (append (encode-symbol (car message) tree)
                (encode (cdr message) tree))))

(define sample-tree
    (make-code-tree (make-leaf 'A 4)
                    (make-code-tree
                        (make-leaf 'B 2)
                        (make-code-tree (make-leaf 'D 1)
                                        (make-leaf 'C 1)))))

(display (encode (list 'A 'D 'A 'B 'B 'C 'A) sample-tree))

(display "\n========================================\n")
